package com.jeff.huawei;

import java.util.HashMap;
import java.util.HashSet;
//采用了深度优先搜索（DFS）的策略，并使用了一个 HashMap 来记录每个石头和它能达到的下一个石头距离的映射关系
public class FrogJump {
    public static boolean canCross(int[] stones) {
        if (stones[1] != 1) {
            return false; // 第一步无法跳到第二块石头
        }

        // 创建一个哈希表，用于存储每个石头及其可以跳的步数
        HashMap<Integer, HashSet<Integer>> stoneMap = new HashMap<>();
        for (int stone : stones) {
            stoneMap.put(stone, new HashSet<>());
        }
        stoneMap.get(stones[0]).add(1); // 从第一块石头开始，可以跳1步

        for (int stone : stones) {
            for (int step : stoneMap.get(stone)) {
                int reach = stone + step;
                if (reach == stones[stones.length - 1]) {
                    return true; // 直接跳到最后一块石头
                }
                // 尝试跳到 reach 的位置
                HashSet<Integer> nextSteps = stoneMap.get(reach);
                if (nextSteps != null) {
                    //只能往前跳
                    if (step - 1 > 0) {
                        nextSteps.add(step - 1);
                    }
                    nextSteps.add(step);
                    nextSteps.add(step + 1);
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        System.out.println(canCross(new int[]{0, 1, 3, 5, 6, 8, 12, 17})); // 应输出 true
        System.out.println(canCross(new int[]{0, 1, 2, 3, 4, 8, 9, 11})); // 应输出 false
    }
}
